package 二分法;

public class searchRange34V2 {
    /**
     * 相当于是找到重复元素的第一个元素和最后一个元素的位置
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange(int[] nums, int target) {
        int leftindex = check(nums, true, target);
        int rightindex = check(nums, false, target) - 1;
        if (leftindex <= rightindex && rightindex < nums.length && nums[leftindex] == target && nums[rightindex] == target) {
            return new int[]{leftindex, rightindex};
        } else {
            return new int[]{-1, -1};
        }
    }

    /**
     * 摘到最左边的数据 和最右边的数据
     *
     * @param nums
     * @param lower
     * @param target
     * @return
     */
    private int check(int[] nums, boolean lower, int target) {
        int left = 0, right = nums.length - 1;
        int ans = nums.length;
        while (left <= right) {
            int mid = (left + right) >> 1;
            // 右边
            if (nums[mid] > target) {
                right = mid - 1;
                ans = mid;
            } else if ((lower && nums[mid] >= target)) {
                // 左边
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}
